# Splay Tree

This is a Java implementation of a [Splay Tree](https://en.wikipedia.org/wiki/Splay_tree "WikiPedia article on Splay Trees"). It is utilized in a fictional "recent contacts" program similar to the one used in Android's starred contacts list.

#### Definition

Splay Trees are [Binary Search Trees](https://en.wikipedia.org/wiki/Binary_search_tree "WikiPedia article on Binary Search Trees") with an added property that any time an element is accessed (search, add, delete) it is then migrated to the root of the tree by way of left&ndash; and right&ndash;rotations:

![https://en.wikipedia.org/wiki/File:Tree_rotation_animation_250x250.gif](tree-rotation.gif "File from Wikimedia Commons")

([Via Wikimedia Commons](https://en.wikipedia.org/wiki/File:Tree_rotation_animation_250x250.gif))

This keeps the most recently used items near the top of the tree, at the expense of keeping the tree quite [degenerate](https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees "Types of Binary Search Trees (BST article on WikiPedia)"). The tree is called a _Splay_ Tree because of how stretched out it can usually get. Nonetheles, because of the [principle of locality](https://en.wikipedia.org/wiki/Locality_of_reference "WikiPedia article on Locality of Reference"), the operations search, insert, and delete all operate on the order of O([lg](https://en.wikipedia.org/wiki/Binary_logarithm "Binary Logarithm (article on WikiPedia)") <i>n</i>) [amortized time](https://en.wikipedia.org/wiki/Amortized_analysis "WikiPedia article on Amortized Analysis"), even though the true worst case is O(<i>n</i>) for all three.

#### Usage

1. Clone the repository
2. Copy the contents of the [src](src/recentContacts "All source code files") directory to your project
3. Instantiate a new Splay Tree in your project

For example, if you want a Splay Tree of type `String`, add this line in your program:

    SplayTree<String> tree = new SplayTree<String>();

###### Public Methods

1. `SplayTree()`, `SplayTree(T d)`, or `SplayTree(Node<T> n)`
2. `addElement(T d)` or `addElement(Node<T> n)`
3. `findElement(T d)` or `findElement(Node<T> n)`
4. `removeElement(T d)` or `removeElement(Node<T> n)`

Look at the contents of the file [RecentContacts.java](src/recentContacts/RecentContacts.java "Source code for this file") for an example use of each of these methods.

#### Testing

Also included in this program are the files used for testing the public methods of the various classes. I built this program using Eclipse and tested it with JUnit. If you wish to run these unit tests, you will need to have JUnit 4+ installed.
